// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include <unordered_map>
#include "commoncppproblem438.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=438 lang=cpp
 *
 * [438] 找到字符串中所有字母异位词
 */

// @lc code=start
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        unordered_map<char, int> need, window;
        for(char c : p)
            need[c]++;

        vector<int> res;        //返回向量

        int right = 0;
        int left = 0;
        int vaild = 0;
        while (right < s.size())
        {
            //c 为右窗口边界
            char c = s[right];

            //右移窗口
            right++;

            //更新右移窗口后的数据
            if(need.count(c))
            {
                window[c]++;
                if(window[c] == need[c])
                {
                    vaild++;
                }
            }

            //判断窗口是否左移，判断条件就是让窗口大小进行固定
            while(right - left >= p.size())
            {
                if(vaild == need.size())
                {
                    res.push_back(left);
                }
                //d是将要左移的窗口
                char d = s[left];

                //左移窗口
                left++;

                //更新左移窗口后的数据
                if(need.count(d))
                {
                    if(window[d] == need[d])
                    {
                        vaild--;
                    }
                    window[d]--;
                }
            }
        }
        return res;
    }
};
// @lc code=end

